#include<iostream>
#include<algorithm>
using namespace std;

int main(void)
{
	const int m = 7;
	const int n = 6;
	
	char x[] = "ABCBDAB";
	char y[] = "BDCABA";
	
	int c[m + 1][n + 1] = {0};
	for (int i = 1; i <= m; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			if (x[i - 1] == y[j - 1])
			{
				c[i][j] = c[i - 1][j - 1] + 1;
			}
			else
			{
				c[i][j] = max(c[i - 1][j], c[i][j - 1]);
			}
		}
	}
	
	char lcs[255] = {0};
	char* pstr = &lcs[254];
	for (int i = m, j = n; i != 0 && j != 0; )
	{
		int len1 = c[i][j - 1];
		int len2 = c[i - 1][j];
		int len3 = c[i - 1][j - 1];
		
		if (c[i][j] == len3 + 1)
		{
			i--;
			j--;
			*(--pstr) = x[i];
		}
		else if (len1 > len2)
		{
			j--;
		}
		else
		{
			i--;
		}
	}
	
	cout<< "The LCS is " << pstr <<endl;
}
